1. Field of the Invention
The present invention is directed to computer systems; and more particularly, it is directed to the tessellation of surfaces using computer systems.
2. Description of the Related Art
Digital image editing is the process of creating and/or modifying digital images using a computer system. Using specialized software programs, users may manipulate and transform images in a variety of ways. These digital image editors may include programs of differing complexity such as limited-purpose programs associated with acquisition devices (e.g., digital cameras and scanners with bundled or built-in programs for managing brightness and contrast); limited editors suitable for relatively simple operations such as rotating and cropping images; and professional-grade programs with large and complex feature sets.
Digital images may include raster graphics, vector graphics, or a combination thereof. Raster graphics data (also referred to herein as bitmaps) may be stored and manipulated as a grid of individual picture elements called pixels. A bitmap may be characterized by its width and height in pixels and also by the number of bits per pixel. Commonly, a color bitmap defined in the RGB (red, green blue) color space may comprise between one and eight bits per pixel for each of the red, green, and blue channels. An alpha channel may be used to store additional data such as per-pixel transparency values.
Vector graphics data may be stored and manipulated as one or more geometric objects built with geometric primitives. The geometric primitives (e.g., points, lines, polygons, Bézier curves, and text characters) may be based upon mathematical equations to represent parts of digital images. The geometric objects may typically be located in two-dimensional or three-dimensional space. Suitable image editors, such as Adobe Illustrator® (available from Adobe Systems, Inc.), may be used to perform operations on these objects. Typical operations include rotation, translation, stretching, skewing, changing depth order, and combining objects with other objects. While raster graphics may often lose apparent quality when scaled to a higher resolution, vector graphics may scale to the resolution of the device on which they are ultimately rendered.
To render vector graphics on raster-based imaging devices (e.g., most display devices and printers), the geometric objects are typically converted to raster graphics data in a process called rasterization. Prior to final rasterization, surfaces defined by the geometric objects may be covered with non-overlapping polygons (e.g., triangles or quadrilaterals) in a process called tessellation. The polygons may also be referred to as tessellae, and the arrangement of non-overlapping polygons may be referred to as a mesh. Each polygon is defined by at least three vertices, and each vertex may be characterized by color and alpha values. Because tessellation of a shaded surface may produce many polygons, a surface may be rendered with fine variations in the color and alpha values.
Each polygon (e.g., quadrilateral) in the surface may be further subdivided into Gouraud shaded triangles for rendering to an output device. A geometric object referred to herein as a parametric surface may be defined by a parametric equation. The parametric equation may involve two parameters such as (u, v). A trimmed parametric surface may include a “hole” in the surface defined by a trim curve. By trimming or cutting out parts of the surface, the trim curve may define which parts of the surface are used. Both the parametric surface and the trim curve may be represented in three dimensions. A similar object may be defined using a non-uniform rational B-spline (NURBS) surface.
Trimmed parametric surfaces pose a problem for typical visualization techniques such as ray-tracing and rasterization. In visualizing a parametric surface using ray-tracing techniques, the determination of whether the ray has intersected the surface within a trimmed region may involve computing the intersection of a ray with the parametric surface followed by a point-in-polygon test. Costly iterative methods are typically used for these ray-patch intersection computations.
Alternatively, in visualizing a parametric surface using rasterization techniques, a pre-process may be performed on the parametric surface to convert it into a collection of rasterizable primitives (e.g., triangles). The rasterization may also include a projection of the trim curve (in 2D or 3D) into the parametric uv space of the surface. This projection step typically requires the use of a root-finding technique (e.g., the Newton-Raphson root-finding method) to find the closest point on the patch for each point on the trim curve. The root-finding technique may comprise a computationally expensive numerical method that is performed iteratively for each point on the trim curve in order to project the trim curve into the parametric uv space of the surface.